package sort;

/**
 * @Author wangtengyu
 * @Create 2018-09-10-13:42 归并排序，主要是分而治之的方式，将大的问题拆成细粒度的子问题，然后子问题得出结果后再合并过来。
 * 合并的判断，while循环里两个条件都有，跳出后再判断没满足哪个while循环
 */
public class MergeSort {


  public void sort(int[] array, int low, int high) {
    int[] temp = new int[array.length];//存放排序好的
    int mid = (low + high) / 2;
    if (low < high) {
      sort(array, low, mid);
      sort(array, mid + 1, high);
      merge(array, low, mid, high, temp);
    }
  }


  public void merge(int[] array, int low, int mid, int high, int[] temp) {
    //定义两个指针，一个从low开始，一个从mid开始
    int i = low;
    int j = mid + 1;

    //定义临时数组的指针
    int t = 0;

    while (i <= mid && j <= high) {
      if (array[i] <= array[j]) {
        temp[t++] = array[i++];
      } else {
        temp[t++] = array[j++];
      }
    }
    //跳出循环 一种情况i>mid,一种情况j>high
    while (i <= mid) {
      temp[t++] = array[i++];
    }
    while (j <= high) {
      temp[t++] = array[j++];
    }

    //到现在完毕了
    t = 0;
    while (low <= high) {
      array[low++] = temp[t++];
    }
  }

  public void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }


  public static void main(String[] args) {
    MergeSort mergeSort = new MergeSort();
    int[] array = new int[]{4, 7, 6, 8, 1, 3, 2, 5};
    mergeSort.sort(array, 0, array.length - 1);
    mergeSort.printArray(array);

  }
}
